#include "leetcode/leecode.h"

class Solution {
public:
    string longestDupSubstring(string s) {
      int len = s.length();
      if(len == 1)
        return s;
      else if(len == 2) {
        if(s[0] == s[1])
          return s;
        else
          return string("");
      }

      string ret;
      ret.resize(len);
      // aba
      int begin = 0, end = 0;
      for(int i = 1; i < len-1; i++) {
        int begin_temp=i, end_temp = i;
        int j = 1;
        while((s[i-j] == s[i+j]) && (i - j >=0) && (i+j < len-1)) {
          begin_temp = i - j;
          end_temp = i + j;
          j++;
        }
        if(end_temp - begin_temp > end - begin) {
          end = end_temp;
          begin = begin_temp;
        }
      }

      // abba
      for(int i = 1; i < len - 1; i++) {
        int begin_temp=i, end_temp = i;
        int j = 1;
        while(s[i-j+1] == s[i+j]) {
          begin_temp = i-j+1;
          end_temp = i+j;
        }
        if(end_temp - begin_temp > end - begin) {
          end = end_temp;
          begin = begin_temp;
        }
      }

      if(begin==end)
        return string("");
      return s.substr(begin, end-begin+1);
    }
};

TEST(longestDupSubstring, longestDupSubstring) {
  GTEST_SKIP();
  Solution s;
  EXPECT_STREQ(s.longestDupSubstring("abcd").data(), "");
  EXPECT_STREQ(s.longestDupSubstring("banana").data(), "ana");
}